The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet. For example, a enqueuing component of such a device receives a stream of various sized packets which are accumulated in an input buffer. Each packet is analyzed, and an appropriate amount of memory space is allocated to store the packet. The packet is stored in memory, while certain attributes (e.g., destination information and other information typically derived from a packet header or other source) are maintained in separate memory. Once the entire packet is written into memory, the packet becomes eligible for processing, and an indicator of the packet is typically placed in an appropriate destination queue for being serviced according to some scheduling methodology.
When there is a contention for resources, such as on output links of a packet switching system or interface or even for compute cycles in a computing device, it is important for resources to be allocated or scheduled according to some fairness policy. Moreover, the amount of work required to schedule and to enqueue and dequeue a packet or other scheduled item is important, especially as the operating rate of systems increase.
Ordinary round-robin (RR) is an algorithm commonly used for sharing a common resource between several clients. All clients are served in a cyclic order. In each round every client will be served if it is eligible. When served, each client is permitted to send one packet. Servicing of queues is simple to implement and can be done in constant time, but, due to the varying size of packets, does not allocate bandwidth fairly.
In some scenarios, high priority (e.g., low latency), guaranteed bandwidth, best effort traffic (e.g., spare bandwidth) and other classifications of traffic compete for a common resource. Various known scheduling algorithms are designed to provide isolation, prioritization, and fair bandwidth allocation to traffic competing for a common resource. These are known as fair queuing algorithms. Some examples are Weighted Fair Queuing (WFQ), Self-Clocked Fair Queuing (SCFQ), and Deficit Round Robin/Surplus Round Robin (referred to as DRR).
WFQ, and SCFQ depend upon arrival times as well as previous link utilization in order to calculate the next best packet to send. The accepted “ideal” behavior is bit-by-bit round robin, which states that the next packet to send should be the packet which would have completed if all packets currently in the system send one bit each round robin (which is typically not practical in a packet based system). The inclusion of arrival times in the scheduling algorithm, in order to calculate theoretical ideal departure times, typically requires insertion into a sorted list which is known to be an O(log N) problem worst case where N is the number of packets already enqueued.
DRR is an algorithm used for sharing a common resource between several clients with different ratios between clients (i.e., some clients are allowed to consume more of the resources than others). The ratio between clients is typically defined by a parameter called a quantum.
DRR services queues using round-robin servicing with a quantum assigned to each queue. Unlike traditional round-robin, multiple packets up to the specified quantum can be sent resulting in each queue sending at least a quantum's worth of bytes. If the quantum for each queue is equal, then each queue will send an equal amount of bandwidth.
This DRR approach works in rounds, where a round is one round-robin iteration over the queues that have items to be sent. Typically, when the queue is scheduled, it is allowed to transmit until its deficit becomes negative, and then the next queue is served. Packets coming in on different flows are stored in different queues. Each round, each queue is allocated a quantum worth of bits, which are added to the deficit of each queue. Each queue is allowed to send out one or more packets in a DRR round, subject to the restriction that it cannot send more bits than indicated by the deficit corresponding to the queue. If there are no more packets in a queue after the queue has been serviced, the deficit corresponding to the queue is set to zero. Otherwise, the remaining amount (i.e., the deficit minus the number of bits sent) is maintained for the next round.
DRR is an algorithm that does not depend upon actual arrival times and has complexity of O(1)—that is the amount of work required is a constant and independent of the number of packets enqueued. In order to be work conserving, a packet should be sent every time a queue is scheduled. Thus, the quantum used in DRR should be at least one maximum packet size (MTU) to guarantee that when the quantum is added to any deficit, the resulting value is at least zero. DRR provides fair bandwidth allocation and is easy to implement. It is work conserving and, because of its O(1) properties, it scales well with higher link speeds and larger number of queues. However, its scheduling behavior deviates quite a bit from the bit-by-bit round robin “ideal”. In particular, latency for a system with N queues is Q*N where Q is the average quantum, which must be at least one maximum transport unit (MTU).
In one implementation, called modified deficit round robin (MDRR), there is optionally one high priority (HP) client mapped to each resource, in addition to the other non-high priority (NHP) clients mapped to the resource. In this implementation there are two possible modes of operation: low latency mode and fair mode. In low latency mode, the HP client is constantly served until it is not eligible (i.e., either it has an empty queue or it had exceeded its allocated bandwidth). The NHP clients are only served whenever the HP client can't be served. Low latency mode reduces the latency of the HP client (good for voice/video applications), but can cause starvation of NHP clients. In fair mode, one packet is sent from the HP client and one from other NHP clients in alternating order as long as the HP client didn't reach its maximum allocated bandwidth. Fair mode is a one compromise point between the requirement not to starve NHP clients and the low latency requirement of HP clients.
In addition to the above described fair queuing algorithm, there is another approach using token buckets that is used to shape traffic. At the start of each cycle, which may be initiated upon expiration of a timer or automatically after a previous cycle is completed, each client is given additional tokens where the tokens represent a number of packets or bytes that a client can send. Thus, the bandwidth allocated to a client is dependent on the number of tokens, and different clients may be given different amounts of tokens. When served, each client is permitted to send the number of packets or bytes or information corresponding to the number of tokens it currently possesses.
In some applications, known scheduling techniques may not result in a sustained volume of processing. For example, in certain situations, a line card has a requisite output packet bandwidth it must sustain to keep up with incoming traffic or for other reasons. These packets may be of varying size and arrival rates. The overhead in scheduling the sending of packets may be of such a nature, that if a certain number of packets or bytes are not sent on the average for each scheduling event, this requisite rate may not be accomplished. Thus, needed are new methods and apparatus for scheduling of processes, such as, but not limited to packets in a packet switching system, which may provide improved performance and/or have other desirable characteristics.